package trees;

import java.util.HashSet;

//Merging 2 binary trees

public class MergeTwoTrees {

	static class Node {
		int value;
		Node left, right;

		public Node(int v) {
			this.value = v;
		}

		public int hashCode() {
			return value;
		}

		public boolean equals(Object obj) {
			if (obj == null) {
				return false;
			}
			if (obj instanceof Node) {
				return value == ((Node) obj).value;
			} else
				return false;
		}
	}

	// Merging 2 binary trees. (I said O(n log n log n) and he was satisfied)
	public static void main(String[] args) {

		Node root1 = new Node(6);
		Node n2 = new Node(5);
		root1.left = n2;
		Node n3 = new Node(8);
		root1.right = n3;
		Node n4 = new Node(9);
		n3.right = n4;
		Node n5 = new Node(11);
		n4.left = n5;
		Node n6 = new Node(19);
		n2.left = n6;

		Node root2 = new Node(4);
		Node n12 = new Node(14);
		root2.left = n12;
		Node n13 = new Node(5);
		root2.right = n13;
		Node n14 = new Node(7);
		n13.right = n14;
		Node n15 = new Node(1);
		n14.left = n15;
		Node n16 = new Node(19);
		n12.left = n16;

		Node root = mergeTrees(root1, root2);

		printTree(root1);

		System.out.println();

		printTree(root);
	}

	private static Node mergeTrees(Node root1, Node root2) {

		if (root1 == null || root2 == null) {
			return root1 == null ? root2 : root1;
		}

		HashSet<Node> set = new HashSet<Node>();

		traverse(root1, set);
		traverse(root2, set);

		return createBinaryTree(set);
	}

	private static Node createBinaryTree(HashSet<Node> set) {

		Node head = null;
		for (Node n : set) {
			n.right = head;
			n.left = null;
			head = n;
		}

		return head;
	}

	private static void traverse(Node n, HashSet<Node> set) {

		if (n != null) {
			set.add(n);
			traverse(n.left, set);
			traverse(n.right, set);
		}
	}

	private static void printTree(Node n) {
		if (n != null) {
			printTree(n.left);
			System.out.print(n.value + " ");
			printTree(n.right);
		}
	}
}
